{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #H-Index II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #binary-search"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #二分查找"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: hIndex"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #H 指数 II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个整数数组 <code>citations</code> ，其中 <code>citations[i]</code> 表示研究者的第 <code>i</code> 篇论文被引用的次数，<code>citations</code> 已经按照&nbsp;<strong>升序排列&nbsp;</strong>。计算并返回该研究者的 h<strong><em>&nbsp;</em></strong>指数。</p>\n",
    "\n",
    "<p><a href=\"https://baike.baidu.com/item/h-index/3991452?fr=aladdin\" target=\"_blank\">h 指数的定义</a>：h 代表“高引用次数”（high citations），一名科研人员的 <code>h</code> 指数是指他（她）的 （<code>n</code> 篇论文中）<strong>至少&nbsp;</strong>有 <code>h</code> 篇论文分别被引用了<strong>至少</strong> <code>h</code> 次。</p>\n",
    "\n",
    "<p>请你设计并实现对数时间复杂度的算法解决此问题。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong class=\"example\">示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong><code>citations = [0,1,3,5,6]</code>\n",
    "<strong>输出：</strong><code>3</code>\n",
    "<strong>解释：</strong>给定数组表示研究者总共有 <code>5</code> 篇论文，每篇论文相应的被引用了 <code>0, 1, 3, 5, 6</code> 次。\n",
    "&nbsp;    由于研究者有<code>3</code>篇论文每篇<strong> 至少 </strong>被引用了 <code>3</code> 次，其余两篇论文每篇被引用<strong> 不多于</strong> <code>3</code> 次，所以她的<em> h </em>指数是 <code>3</code> 。</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong><code>citations = [1,2,100]</code>\n",
    "<strong>输出：</strong><code>2</code>\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == citations.length</code></li>\n",
    "\t<li><code>1 &lt;= n &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>0 &lt;= citations[i] &lt;= 1000</code></li>\n",
    "\t<li><code>citations</code> 按 <strong>升序排列</strong></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [h-index-ii](https://leetcode.cn/problems/h-index-ii/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [h-index-ii](https://leetcode.cn/problems/h-index-ii/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[0,1,3,5,6]', '[1,2,100]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hIndex(self, citations: List[int]) -> int:\n",
    "        left = 1\n",
    "        n = right = len(citations)\n",
    "        \n",
    "        while left <= right:  # 区间不为空\n",
    "            # 循环不变量：\n",
    "            # left-1 的回答一定为「是」\n",
    "            # right+1 的回答一定为「否」\n",
    "            mid = left +(right-left)//2\n",
    "            # 引用次数最多的 mid 篇论文，引用次数均 >= mid\n",
    "            if citations[n-mid] >= mid:\n",
    "                left = mid + 1  # 询问范围缩小到 [mid+1, right]\n",
    "            else:\n",
    "                right = mid - 1  # 询问范围缩小到 [left, mid-1]\n",
    "        # 循环结束后 right 等于 left-1，回答一定为「是」\n",
    "        # 根据循环不变量，right 现在是最大的回答为「是」的数\n",
    "        return right\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hIndex(self, citations: List[int]) -> int:\n",
    "        n = len(citations)\n",
    "        for i in range(n):\n",
    "            if citations[n-i-1]<=i:\n",
    "                return i\n",
    "        return n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hIndex(self, citations: List[int]) -> int:\n",
    "        n = len(citations)\n",
    "        for i in range(1, n + 1):\n",
    "            if citations[-i] < i:\n",
    "                return i - 1\n",
    "            else:\n",
    "                continue\n",
    "        return n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hIndex(self, citations: List[int]) -> int:\n",
    "        pop_cnt = 0\n",
    "        while citations:\n",
    "            cit = citations.pop(-1)\n",
    "            pop_cnt += 1\n",
    "            if cit < pop_cnt:\n",
    "                pop_cnt -= 1\n",
    "                break\n",
    "\n",
    "        return pop_cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hIndex(self, citations: List[int]) -> int:\n",
    "        n = len(citations)\n",
    "        l, r = 0, n\n",
    "        while l < r:\n",
    "            mid = l + r + 1 >> 1\n",
    "            if citations[-mid] >= mid:\n",
    "                l = mid\n",
    "            else:\n",
    "                r = mid - 1 \n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hIndex(self, citations: List[int]) -> int:\n",
    "        # 二分\n",
    "        n = len(citations)\n",
    "        l, r = 0, n\n",
    "        while l < r:\n",
    "            m = (l + r +1) // 2\n",
    "            if citations[-m] >= m:\n",
    "                l = m\n",
    "            else:\n",
    "                r = m - 1\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hIndex(self, citations: List[int]) -> int:\n",
    "        h = len(citations)\n",
    "        if citations[-1] == 0:\n",
    "            return 0\n",
    "        for i in citations:\n",
    "            if i >= h:\n",
    "                return h\n",
    "            h -= 1\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hIndex(self, citations: List[int]) -> int:\n",
    "        # 在区间 [left, right] 内询问\n",
    "        left = 1\n",
    "        right = len(citations)\n",
    "        while left <= right:  # 区间不为空\n",
    "            # 循环不变量：\n",
    "            # left-1 的回答一定为「是」\n",
    "            # right+1 的回答一定为「否」\n",
    "            mid = (left + right) // 2\n",
    "            # 引用次数最多的 mid 篇论文，引用次数均 >= mid\n",
    "            if citations[-mid] >= mid:\n",
    "                left = mid + 1  # 询问范围缩小到 [mid+1, right]\n",
    "            else:\n",
    "                right = mid - 1  # 询问范围缩小到 [left, mid-1]\n",
    "        # 循环结束后 right 等于 left-1，回答一定为「是」\n",
    "        # 根据循环不变量，right 现在是最大的回答为「是」的数\n",
    "        return right\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hIndex(self, citations: List[int]) -> int:\n",
    "        n = len(citations)\n",
    "        l = 0\n",
    "        r = n - 1\n",
    "        while l <= r:\n",
    "            mid = (l + r + 1) // 2\n",
    "            if citations[mid] < n - mid:\n",
    "                l = mid + 1\n",
    "            else:\n",
    "                r = mid - 1\n",
    "        return n - l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hIndex(self, citations: List[int]) -> int:\n",
    "        n = len(citations)\n",
    "        left = 0; right = n - 1\n",
    "        while left <= right:\n",
    "            mid = left + (right - left) // 2\n",
    "            if citations[mid] >= n - mid:\n",
    "                right = mid - 1\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        return n - left\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hIndex(self, citations) -> int:\n",
    "        if len(citations) == 1:\n",
    "            return min(citations[0], 1)\n",
    "        left = 0\n",
    "        right = len(citations)-1\n",
    "        # mid = (left+right-1)//2 \n",
    "        mid = (left+right)//2 \n",
    "\n",
    "        tmp =  0\n",
    "        while(left <= right):\n",
    "            print(left, mid, right)\n",
    "            if citations[mid] == len(citations)-mid:\n",
    "                return len(citations)-mid \n",
    "            elif citations[mid] > len(citations)-mid:\n",
    "                tmp = max(tmp, min(citations[mid], len(citations)-mid))\n",
    "                right = mid-1\n",
    "                # mid = (right+left-1)//2\n",
    "                mid = (left+right)//2 \n",
    "            else:\n",
    "                tmp = max(tmp, min(citations[mid], len(citations)-mid))\n",
    "\n",
    "                left = mid+1\n",
    "                # mid = (right+left-1)//2\n",
    "                mid = (left+right)//2 \n",
    "        return tmp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hIndex(self, citations: List[int]) -> int:\n",
    "        n = len(citations)\n",
    "        low = 0\n",
    "        high = n - 1\n",
    "        while low <= high:\n",
    "            mid = (low + high) // 2\n",
    "            if citations[mid] < n - mid:\n",
    "                low = mid + 1\n",
    "            elif citations[mid] == n - mid:\n",
    "                return n - mid\n",
    "            else:\n",
    "                high = mid - 1\n",
    "        return n - low\n",
    "\n",
    "                \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hIndex(self, citations: List[int]) -> int:\n",
    "        citations.sort()\n",
    "        len_ = len(citations)\n",
    "        for loc,num in enumerate(citations):\n",
    "            if num >= len_-loc:\n",
    "                return len_-loc\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hIndex(self, citations: List[int]) -> int:\n",
    "        n = len(citations)\n",
    "        lf, rf, ans = 1, n, 0\n",
    "        while lf <= rf:\n",
    "            cf = (lf + rf) >> 1\n",
    "            if citations[n - cf] >= cf:\n",
    "                ans, lf = cf, cf + 1\n",
    "            else:\n",
    "                rf = cf - 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hIndex(self, citations: List[int]) -> int:\n",
    "        for i, v in enumerate(citations):\n",
    "            if len(citations) - i <= v:\n",
    "                return len(citations) - i\n",
    "        \n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hIndex(self, citations: List[int]) -> int:\n",
    "        n = len(citations)\n",
    "        l, r = 0, n + 1\n",
    "\n",
    "        while l <= r:\n",
    "            mid = (l + r) // 2\n",
    "            loc = bisect.bisect_left(citations, mid)\n",
    "            if (n - loc) == mid: return mid\n",
    "            elif (n - loc) < mid: r = mid - 1\n",
    "            else: l = mid + 1\n",
    "        return r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hIndex(self, citations: List[int]) -> int:\n",
    "        n = len(citations)\n",
    "        ans = 0\n",
    "        for i, c in enumerate(citations):\n",
    "            ans = max(ans, min(n - i, c))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hIndex(self, citations: List[int]) -> int:\n",
    "        if len(citations) == 1:\n",
    "            if citations[0] == 0:\n",
    "                return 0\n",
    "            else:\n",
    "                return 1\n",
    "        left = 0\n",
    "        right = len(citations) - 1\n",
    "        a_len = len(citations)\n",
    "        while left <= right:\n",
    "            mid = (right - left) // 2 + left\n",
    "            valid_num = a_len - mid\n",
    "            mid_val = citations[mid]\n",
    "            if mid_val < valid_num:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid -1\n",
    "                 \n",
    "        return a_len - left\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hIndex(self, citations: List[int]) -> int:\n",
    "        ans = 0\n",
    "        n = len(citations)\n",
    "        left = 1\n",
    "        right = n\n",
    "        while left<=right:\n",
    "            mid = (left+right)//2\n",
    "            if citations[-mid]>=mid:\n",
    "                left = mid+1\n",
    "            else:\n",
    "                right = mid-1\n",
    "        return right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hIndex(self, citations: List[int]) -> int:\n",
    "        n = len(citations)\n",
    "        left = 0; right = n - 1\n",
    "        while left <= right:\n",
    "            mid = left + (right - left) // 2\n",
    "            if citations[mid] >= n - mid:\n",
    "                right = mid - 1\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        return n - left\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hIndex(self, citations: List[int]) -> int:\n",
    "        h=0\n",
    "        for i in range(len(citations)-1,-1,-1):\n",
    "            if citations[i]>h:\n",
    "                h+=1\n",
    "        return h"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hIndex(self, citations: List[int]) -> int:\n",
    "\n",
    "        left = 0\n",
    "        right = len(citations) - 1\n",
    "        while(left < right):\n",
    "            mid = (left + right) // 2\n",
    "            if citations[mid] >= len(citations) - mid:\n",
    "                right = mid\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        assert left == right\n",
    "\n",
    "        if citations[left] == 0:\n",
    "            return 0\n",
    "\n",
    "        return len(citations) - left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hIndex(self, citations: List[int]) -> int:\n",
    "        n = len(citations)\n",
    "        left = 0\n",
    "        right = n-1\n",
    "        while left <= right:\n",
    "            mid = (left+right)//2\n",
    "            if(citations[mid]>=n-mid):\n",
    "                right = mid - 1\n",
    "            else :\n",
    "                left = mid + 1\n",
    "        return n-left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # def hIndex(self, citations: List[int]) -> int:  #闭区间写法\n",
    "    #     left = 1\n",
    "    #     right = len(citations)\n",
    "    #     while left <= right:\n",
    "    #         mid = (left + right)//2\n",
    "    #         if citations[len(citations)-mid] >= mid:\n",
    "    #             left = mid +1\n",
    "    #         else:\n",
    "    #             right = mid -1\n",
    "    #     return right\n",
    "    # def hIndex(self, citations: List[int]) -> int:  #左闭右开区间写法\n",
    "    #     left = 1\n",
    "    #     right = len(citations) + 1\n",
    "    #     while left < right:\n",
    "    #         mid = (left + right)//2\n",
    "    #         if citations[len(citations)-mid] >= mid:\n",
    "    #             left = mid +1\n",
    "    #         else:\n",
    "    #             right = mid\n",
    "    #     return left - 1\n",
    "    #  def hIndex(self, citations: List[int]) -> int:  #左开右闭区间写法\n",
    "    #     left = 0\n",
    "    #     right = len(citations)\n",
    "    #     while left < right:\n",
    "    #         mid = (left + right +1)//2\n",
    "    #         if citations[len(citations)-mid] >= mid:\n",
    "    #             left = mid \n",
    "    #         else:\n",
    "    #             right = mid -1\n",
    "    #     return left\n",
    "    def hIndex(self, citations: List[int]) -> int:  #开区间写法\n",
    "        left = 0\n",
    "        right = len(citations)+1\n",
    "        while left + 1< right:\n",
    "            mid = (left + right)//2\n",
    "            if citations[len(citations)-mid] >= mid:\n",
    "                left = mid \n",
    "            else:\n",
    "                right = mid \n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hIndex(self, citations: List[int]) -> int:\n",
    "        length=len(citations)\n",
    "        left=0;right=length-1\n",
    "        result=0\n",
    "        while left<=right:\n",
    "            mid=(left+right)//2\n",
    "            if citations[mid]>=length-mid:\n",
    "                result=length-mid\n",
    "                right=mid-1\n",
    "            else:\n",
    "                left=mid+1\n",
    "        return result\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hIndex(self, citations: List[int]) -> int:\n",
    "\n",
    "        n = len(citations)\n",
    "        l, r = 0, n\n",
    "        # 闭区间\n",
    "        # 求满足citations[-i] >= i的最大i\n",
    "        # 即citations[-i] < i + 1的最小i\n",
    "        while l <= r:\n",
    "            mid = (l + r) // 2\n",
    "            if citations[-mid] > mid-1:\n",
    "                l = mid + 1\n",
    "            else:\n",
    "                r = mid - 1\n",
    "        return (l) - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hIndex(self, citations: List[int]) -> int:\n",
    "        n = len(citations)\n",
    "        left, right = 0, n-1\n",
    "\n",
    "        #if n == 1 and citations[0] == 0:\n",
    "        #    return 0\n",
    "\n",
    "        while left <= right:\n",
    "            \n",
    "            #print(left, right)\n",
    "            if citations[(left + right)//2] < n-(left + right)//2:\n",
    "                left = (left + right)//2 + 1\n",
    "            else:\n",
    "                right = (left + right)//2 - 1\n",
    "            '''\n",
    "            mid = left + (right - left) // 2\n",
    "            if citations[mid] >= n - mid:\n",
    "                right = mid - 1\n",
    "            else:\n",
    "                left = mid + 1\n",
    "            '''\n",
    "\n",
    "        return n-left\n",
    "        #print(left, right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hIndex(self, citations: List[int]) -> int:\n",
    "        left = 0\n",
    "        right = len(citations)\n",
    "        while left <= right:\n",
    "            mid = (left + right) // 2\n",
    "            if citations[-mid] >= mid:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        return right\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hIndex(self, citations: List[int]) -> int:\n",
    "        Hvalue = float('-inf')\n",
    "        length = len(citations)\n",
    "        for i in range(length):\n",
    "            Min = min(citations[i],length-i)\n",
    "            if Min >Hvalue:\n",
    "                Hvalue = Min\n",
    "        \n",
    "        return Hvalue"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hIndex(self, citations: List[int]) -> int:\n",
    "        n=len(citations)\n",
    "        left=0#左边闭区间\n",
    "        right=len(citations)-1#右边开区间\n",
    "        while left<=right:\n",
    "            mid=(left+right)//2\n",
    "        #引用次数大于下标\n",
    "            if citations[mid]>=n-mid:\n",
    "                right=mid-1\n",
    "            else:\n",
    "                left=mid+1\n",
    "        return n-left\n",
    "        \n",
    "        \n",
    "\n",
    "        \n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hIndex(self, citations: List[int]) -> int:\n",
    "        n = len(citations)\n",
    "        left = 0; right = n - 1\n",
    "        while left <= right:\n",
    "            mid = left + (right - left) // 2\n",
    "            if citations[mid] >= n - mid:\n",
    "                right = mid - 1\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        return n - left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hIndex(self, citations: List[int]) -> int:\n",
    "        n=len(citations)\n",
    "        for idx,val in enumerate(citations):\n",
    "            if n-idx<=val:\n",
    "                return n-idx\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hIndex(self, citations: List[int]) -> int:\n",
    "        h = 0\n",
    "        for i in range(1,len(citations)+1):\n",
    "            if citations[-i]>h:\n",
    "                h+=1\n",
    "            else:\n",
    "                break\n",
    "        return h\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hIndex(self, citations: List[int]) -> int:\n",
    "        res = 0\n",
    "        citations.sort()\n",
    "        left = 0\n",
    "        n = len(citations)\n",
    "        right = n - 1\n",
    "        while left <= right:\n",
    "            mid = (left + right) // 2\n",
    "            if citations[mid] < n - mid:\n",
    "                res = max(res, citations[mid])\n",
    "                left = mid + 1\n",
    "            else :\n",
    "                res = max(res, n - mid)\n",
    "                right = mid - 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hIndex(self, citations: List[int]) -> int:\n",
    "        n = len(citations)\n",
    "        left, right = 0, n\n",
    "        while left < right:\n",
    "            mid = (left + right + 1) >> 1\n",
    "            if citations[n - mid] >= mid:\n",
    "                left = mid\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hIndex(self, citations: List[int]) -> int:\n",
    "        n = len(citations)\n",
    "        if citations[0] >= n:\n",
    "            return n\n",
    "        while  n >= 0:\n",
    "            n -= 1\n",
    "            if citations[-n] >= n:\n",
    "                return n\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hIndex(self, citations: List[int]) -> int:\n",
    "        left = 1\n",
    "        right = len(citations)\n",
    "        while left <= right:\n",
    "            mid = (left + right) // 2\n",
    "            # 引用次数最多的 mid 篇论文，引用次数均 >= mid\n",
    "            if citations[-mid] >= mid:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        return right\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hIndex(self, citations: List[int]) -> int:\n",
    "        # 在区间 (left, right) 内询问\n",
    "        left = 0\n",
    "        right = len(citations) + 1\n",
    "        while left + 1 < right:  # 区间不为空\n",
    "            # 循环不变量：\n",
    "            # left 的回答一定为「是」\n",
    "            # right 的回答一定为「否」\n",
    "            mid = (left + right) // 2\n",
    "            # 引用次数最多的 mid 篇论文，引用次数均 >= mid\n",
    "            if citations[-mid] >= mid:\n",
    "                left = mid  # 询问范围缩小到 (mid, right)\n",
    "            else:\n",
    "                right = mid  # 询问范围缩小到 (left, mid)\n",
    "        # 根据循环不变量，left 现在是最大的回答为「是」的数\n",
    "        return left\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hIndex(self, citations: List[int]) -> int:\n",
    "        left = 1\n",
    "        right = len(citations)\n",
    "        while left <= right: # 区间不等于0      \n",
    "            mid = (left + right) // 2 \n",
    "            if citations[-mid] >= mid:          \n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        return right             "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hIndex(self, citations: List[int]) -> int:\n",
    "        #[1, n]\n",
    "        #(0, n + 1)\n",
    "        left = 0\n",
    "        right = len(citations) + 1\n",
    "        \n",
    "        while left + 1 < right:\n",
    "            mid = (left + right) // 2\n",
    "            if citations[-mid] >= mid:\n",
    "                left = mid\n",
    "            else:\n",
    "                right = mid\n",
    "                \n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hIndex(self, citations: List[int]) -> int:\n",
    "        n = len(citations)\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            ans = max(ans,min(n-i,citations[i]))\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hIndex(self, citations: List[int]) -> int:\n",
    "        # 在区间 [left, right] 内询问\n",
    "        left = 1\n",
    "        right = len(citations)\n",
    "        while left <= right:  # 区间不为空\n",
    "            # 循环不变量：\n",
    "            # left-1 的回答一定为「是」\n",
    "            # right+1 的回答一定为「否」\n",
    "            mid = (left + right) // 2\n",
    "            # 引用次数最多的 mid 篇论文，引用次数均 >= mid\n",
    "            if citations[-mid] >= mid:\n",
    "                left = mid + 1  # 询问范围缩小到 [mid+1, right]\n",
    "            else:\n",
    "                right = mid - 1  # 询问范围缩小到 [left, mid-1]\n",
    "        # 循环结束后 right 等于 left-1，回答一定为「是」\n",
    "        # 根据循环不变量，right 现在是最大的回答为「是」的数\n",
    "        return right\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hIndex(self, citations: List[int]) -> int:\n",
    "        l = len(citations)\n",
    "        if l == 1:\n",
    "            if max(citations)==0:\n",
    "                return 0\n",
    "        for i in range(l-1,-1,-1):\n",
    "            if citations[i] < l - i:\n",
    "                return l-i-1\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hIndex(self, citations: List[int]) -> int:\n",
    "        citations.sort(reverse=True)\n",
    "        length=len(citations)\n",
    "        for i in range(length):\n",
    "            if i+1>citations[i]:\n",
    "                return i\n",
    "        return length\n",
    "\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hIndex(self, citations: List[int]) -> int:\n",
    "        length = len(citations)\n",
    "        if length == 0:\n",
    "            return 0\n",
    "\n",
    "        lastCount = -1\n",
    "        for i in range(length, 0, -1):\n",
    "            if citations[0-i] >= i:\n",
    "                return i\n",
    "        return 0\n",
    "\n",
    "    \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hIndex(self, citations: List[int]) -> int:\n",
    "        n = len(citations)\n",
    "        left, right = 0, n - 1\n",
    "        while left < right:\n",
    "            mid = (left + right) // 2\n",
    "            if citations[mid] >= n - mid:\n",
    "                right = mid\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        return n - right if citations[right] >= n - right else 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hIndex(self, citations: List[int]) -> int:\n",
    "        num=len(citations)\n",
    "        h=0\n",
    "        for t in range(1,num+1):\n",
    "            if citations[num-t]>=t:\n",
    "                h=t\n",
    "                continue\n",
    "            else:\n",
    "                break\n",
    "        return h\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hIndex(self, citations: List[int]) -> int:\n",
    "        n = len(citations)\n",
    "        left = 0\n",
    "        right = n - 1\n",
    "        while left <= right:\n",
    "            mid = left + (right - left) // 2\n",
    "            if citations[mid] >= n - mid:\n",
    "                right = mid - 1\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        return n - left\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "思路：\n",
    "https://leetcode.cn/problems/h-index-ii/solutions/870989/h-zhi-shu-ii-by-leetcode-solution-si7h/\n",
    "https://mp.weixin.qq.com/s/zqjwHcW7QmuRzl0zWr5NHA\n",
    "使用二分查找法解决。\n",
    "当遇到第一个无法满足的数时，更大的数值就没必要找了。一个简单的推导：至少出现k次的论文数不足k篇 >= 至少出现k+1次的论文必然不足k篇 >= 至少出现k+1次的论文必然不足k+1篇。\n",
    "数组citations已经按照升序排序(关键)，每次在查找范围内取中点mid，则有n−mid篇论文被引用了至少citations[mid]次。如果在查找过程中满足citations[mid]≥n−mid，则移动右边界right，否则移动左边界left。\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def hIndex(self, citations: List[int]) -> int:\n",
    "        n = len(citations)\n",
    "        left = 0\n",
    "        right = n - 1\n",
    "        while left <= right:\n",
    "            mid = left + (right - left) // 2\n",
    "            if citations[mid] >= n - mid:\n",
    "                right = mid - 1\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        return n - left\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hIndex(self, citations: List[int]) -> int:\n",
    "        #\n",
    "        index = 0\n",
    "        length = len(citations)\n",
    "        h = 0\n",
    "        start = 0\n",
    "        end = length - 1\n",
    "        if(citations[start]>length):\n",
    "            return length\n",
    "        if(start == end):\n",
    "            return min(citations[start],1)\n",
    "        mid = int((start+end)/2)\n",
    "        while(start<end):\n",
    "            print(f'mid{mid}')\n",
    "            print(f'h{h}')\n",
    "            if citations[mid]>(length-mid):\n",
    "                h = max(h,length-mid)\n",
    "                end = mid\n",
    "                mid = int((start+end)/2)\n",
    "                print(f'c>len {h}')\n",
    "            else :\n",
    "                h = max(h,citations[mid])\n",
    "                start = mid + 1\n",
    "                mid = int((start+end)/2)\n",
    "                print(f'c<=len {h}')\n",
    "        h = max(h,min(citations[start],length-mid))\n",
    "        return h \n",
    "\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def hIndex(self, citations: List[int]) -> int:\n",
    "        n = len(citations)\n",
    "        left = 0\n",
    "        right = n - 1\n",
    "        while left <= right:\n",
    "            mid = (left + right) // 2\n",
    "            if citations[mid] < n - mid:\n",
    "                left = mid + 1\n",
    "            else: \n",
    "                right = mid - 1\n",
    "        return n - left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hIndex(self, citations: List[int]) -> int:\n",
    "        n = len(citations)\n",
    "        if n == 1: return 1 if citations[0] > 0 else 0\n",
    "        left, right = 1, min(n, 1000)\n",
    "\n",
    "        def check(target):\n",
    "            idx = n - target\n",
    "            return citations[idx] >= target\n",
    "\n",
    "        while left <= right:\n",
    "            mid = left + right >> 1\n",
    "            if check(mid):\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        return left - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hIndex(self, citations: List[int]) -> int:\n",
    "        i = 1\n",
    "        j = n = len(citations)\n",
    "\n",
    "        while i <= j:\n",
    "            mid = (i + j) // 2\n",
    "            if citations[-mid] >= mid:\n",
    "                i = mid + 1\n",
    "            else:\n",
    "                j = mid - 1\n",
    "        return j\n",
    "\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hIndex(self, citations: List[int]) -> int:\n",
    "        n = len(citations)\n",
    "        left = 0\n",
    "        right = n\n",
    "        while left<=right:\n",
    "            mid = (left+right)//2\n",
    "            if mid<=citations[-mid]:\n",
    "                 left = mid+1\n",
    "            else:\n",
    "                right = mid -1\n",
    "        return right\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hIndex(self, citations: List[int]) -> int:\n",
    "        left = 1\n",
    "        right = len(citations)\n",
    "        while left <= right:\n",
    "            mid = (left + right) // 2\n",
    "            # 引用次数最多的 mid 篇论文，引用次数均 >= mid\n",
    "            if citations[-mid] >= mid:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        return right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hIndex(self, citations: List[int]) -> int:\n",
    "        l = len(citations)\n",
    "        res = 0\n",
    "        for i in range(l):\n",
    "            if citations[i] >= l - i:\n",
    "                res = max(l - i, res)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hIndex(self, citations: List[int]) -> int:\n",
    "        left, right = 0, len(citations)\n",
    "        n = len(citations)\n",
    "        while left<=right:\n",
    "            mid = (left+right)//2\n",
    "            target = n-mid\n",
    "            if citations[-mid]>=mid:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        # left - 1都是 “是”\n",
    "        # right 右边都是 “不是”\n",
    "        return right\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hIndex(self, citations: List[int]) -> int:\n",
    "        n = len(citations)\n",
    "        count = 0\n",
    "        i = n - 1\n",
    "        while i >= 0 and citations[i] > count:\n",
    "            count += 1\n",
    "            i -= 1\n",
    "        return count\n",
    "         \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hIndex(self, citations: List[int]) -> int:\n",
    "        def blue_red(nums, target):\n",
    "            left = 0\n",
    "            right = len(nums) - 1\n",
    "            while left <= right:\n",
    "                mid = (left + right) // 2\n",
    "                if nums[mid] < target:\n",
    "                    left = mid + 1\n",
    "                else:\n",
    "                    right = mid - 1\n",
    "            return left\n",
    "        left = 0\n",
    "        right = n = len(citations)\n",
    "        while left <= right:\n",
    "            mid = (left + right) // 2\n",
    "            if n - blue_red(citations, mid) >= mid:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        return right      "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def hIndex(self, citations: List[int]) -> int:\n",
    "        max_index = 0\n",
    "        for middle_index in range(len(citations)):\n",
    "            # middle_index = len(tem_list) // 2\n",
    "            tem_article_number = middle_index + 1\n",
    "            satisfied_article_number = len(citations) - self.search_satisfied_article_number(citations,\n",
    "                                                                                             tem_article_number)\n",
    "\n",
    "            if tem_article_number <= satisfied_article_number:\n",
    "                 max_index = max(tem_article_number, max_index)\n",
    "            else:\n",
    "                break\n",
    "\n",
    "        return max_index\n",
    "\n",
    "    def search_satisfied_article_number(self, citations, tem_article_number):\n",
    "        if tem_article_number in citations:\n",
    "            return citations.index(tem_article_number)\n",
    "\n",
    "        tem_list = citations\n",
    "        tem_index = 0\n",
    "        while 1:\n",
    "            middle_index = len(tem_list) // 2\n",
    "            if len(tem_list) == 2:\n",
    "                if tem_list[0] > tem_article_number:\n",
    "                    return tem_index\n",
    "                elif tem_list[0] < tem_article_number < tem_list[1]:\n",
    "                    return tem_index + 1\n",
    "                else:\n",
    "                    return tem_index + 2\n",
    "\n",
    "            if tem_list[middle_index] < tem_article_number:\n",
    "                if len(tem_list) == 1:\n",
    "                    return middle_index + 1\n",
    "                tem_index += middle_index\n",
    "                tem_list = tem_list[middle_index::]\n",
    "            elif tem_list[middle_index] > tem_article_number:\n",
    "                tem_list = tem_list[:middle_index + 1:]\n",
    "                if len(tem_list) == 1:\n",
    "                    return middle_index"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hIndex(self, citations: List[int]) -> int:\n",
    "        left=1\n",
    "        n=len(citations)\n",
    "        right=n\n",
    "        ans=0\n",
    "        while left<=right:\n",
    "            mid=(left+right)//2\n",
    "            if citations[-mid]>=mid:\n",
    "                left+=1\n",
    "            else:\n",
    "                right-=1\n",
    "        return right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hIndex(self, citations: List[int]) -> int:\n",
    "        n = len(citations)\n",
    "        left = 0\n",
    "        right = len(citations)\n",
    "        if right==0:\n",
    "            return 0 if citations[0]==0 else 1\n",
    "        while left<right:\n",
    "            mid = (right+left)//2\n",
    "            if citations[mid]<n-mid:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid\n",
    "        return n-left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hIndex(self, citations: List[int]) -> int:\n",
    "        k=len(citations)\n",
    "        l=0\n",
    "        r=k-1\n",
    "        h=0\n",
    "        while l<=r:\n",
    "            m=l+(r-l)//2\n",
    "            p=k-m\n",
    "            #print(p,m)\n",
    "            if citations[m]==p:\n",
    "                h=p\n",
    "                break\n",
    "            elif citations[m]>p:\n",
    "                h=max(h,p)\n",
    "                r=m-1\n",
    "            else:\n",
    "                h=max(h,citations[m])\n",
    "                l=m+1\n",
    "        return h\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hIndex(self, citations: List[int]) -> int:\n",
    "        n = len(citations)\n",
    "        left, right = 0, n\n",
    "        while left < right:\n",
    "            mid = (left + right + 1) // 2\n",
    "            if sum(i >= mid for i in citations) >= mid:\n",
    "                left = mid\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        return right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hIndex(self, citations: List[int]) -> int:\n",
    "        left = 1\n",
    "        right = len(citations)\n",
    "        while left <= right:\n",
    "            mid = (left + right) // 2\n",
    "            if citations[-mid] >= mid:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        return left - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hIndex(self, citations: List[int]) -> int:\n",
    "        # 二分查找\n",
    "        n = len(citations)\n",
    "        l,r = 0,n-1\n",
    "        while l<=r:\n",
    "            m = (l+r)//2\n",
    "            if citations[m] >= n-m:\n",
    "                r = m -1\n",
    "            else:\n",
    "                l = m + 1\n",
    "        return n - l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hIndex(self, cs: List[int]) -> int:\n",
    "        n = len(cs)\n",
    "        l, r = 0, n - 1\n",
    "        while l < r:\n",
    "            mid = l + r >> 1\n",
    "            if cs[mid] >= n - mid:\n",
    "                r = mid\n",
    "            else:\n",
    "                l = mid + 1\n",
    "        return n - r if cs[r] >= n - r else 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hIndex(self, citations: List[int]) -> int:\n",
    "        n = len(citations)\n",
    "        left, right = 0, n\n",
    "        while left < right:\n",
    "            mid = (left + right + 1) >> 1\n",
    "            if citations[n - mid] >= mid:\n",
    "                left = mid\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        return left\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hIndex(self, citations: List[int]) -> int:\n",
    "        # 在区间 (left, right) 内询问\n",
    "        left = 0\n",
    "        right = len(citations) + 1\n",
    "        while left + 1 < right:  # 区间不为空\n",
    "            # 循环不变量：\n",
    "            # left 的回答一定为「是」\n",
    "            # right 的回答一定为「否」\n",
    "            mid = (left + right) // 2\n",
    "            # 引用次数最多的 mid 篇论文，引用次数均 >= mid\n",
    "            if citations[-mid] >= mid:\n",
    "                left = mid  # 询问范围缩小到 (mid, right)\n",
    "            else:\n",
    "                right = mid  # 询问范围缩小到 (left, mid)\n",
    "        # 根据循环不变量，left 现在是最大的回答为「是」的数\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hIndex(self, citations: List[int]) -> int:\n",
    "        left = 1\n",
    "        right = len(citations)\n",
    "        while left <= right:  # 区间不为空\n",
    "            # 循环不变量：\n",
    "            # left-1 的回答一定为「是」\n",
    "            # right+1 的回答一定为「否」\n",
    "            mid = (left + right) // 2\n",
    "            # 引用次数最多的 mid 篇论文，引用次数均 >= mid\n",
    "            if citations[-mid] >= mid:\n",
    "                left = mid + 1  # 询问范围缩小到 [mid+1, right]\n",
    "            else:\n",
    "                right = mid - 1  # 询问范围缩小到 [left, mid-1]\n",
    "        # 循环结束后 right 等于 left-1，回答一定为「是」\n",
    "        # 根据循环不变量，right 现在是最大的回答为「是」的数\n",
    "        return right\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hIndex(self, citations: List[int]) -> int:\n",
    "        n = len(citations)\n",
    "        left, right = 1, min(n, 1000)\n",
    "\n",
    "        def check(target):\n",
    "            idx = n - target\n",
    "            return citations[idx] >= target\n",
    "\n",
    "        while left <= right:\n",
    "            mid = left + right >> 1\n",
    "            if check(mid):\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        return left - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hIndex(self, citations: List[int]) -> int:\n",
    "        i = 1\n",
    "        j = n = len(citations)\n",
    "\n",
    "        while i <= j:\n",
    "            mid = (i + j) // 2\n",
    "            print(n-mid)\n",
    "            if citations[-mid] >= mid:\n",
    "                i = mid + 1\n",
    "            else:\n",
    "                j = mid - 1\n",
    "        return j\n",
    "\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hIndex(self, citations: List[int]) -> int:\n",
    "    \n",
    "        n=len(citations)\n",
    "        citations=citations[-1::-1]\n",
    "        for i in range(n):\n",
    "            if i<n-1 and citations[i]>=i+1:\n",
    "                continue\n",
    "            elif i==n-1 and citations[i]>=i+1:\n",
    "                return i+1\n",
    "            else:\n",
    "                return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hIndex(self, citations: List[int]) -> int:\n",
    "        left = 0\n",
    "        right = len(citations) - 1\n",
    "        while left <= right:\n",
    "            middle = (left + right) // 2\n",
    "            if citations[middle] >= len(citations) - middle:\n",
    "                right = middle - 1\n",
    "            else:\n",
    "                left = middle + 1\n",
    "        return len(citations) - left\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hIndex(self, citations: List[int]) -> int:\n",
    "        left = 1\n",
    "        right = n = len(citations)\n",
    "        while left<=right:\n",
    "            mid = (left+right)>>1\n",
    "            if citations[n-mid]< mid:\n",
    "                right = mid-1\n",
    "            else:\n",
    "                left = mid+1\n",
    "        return right\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hIndex(self, citations: List[int]) -> int:\n",
    "        left = 1\n",
    "        right = len(citations)\n",
    "        while left<=right:\n",
    "            mid = (left+right)//2\n",
    "            if citations[-mid] >= mid:\n",
    "                left = mid+1\n",
    "            else:\n",
    "                right = mid-1\n",
    "        return right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hIndex(self, citations: List[int]) -> int:\n",
    "        n=len(citations)\n",
    "        l=0\n",
    "        r=n+1\n",
    "        while l<r:\n",
    "            mid=l+r>>1\n",
    "            if citations[-mid]>=mid:\n",
    "                l=mid+1\n",
    "            else:\n",
    "                r=mid\n",
    "        return l-1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hIndex(self, citations: List[int]) -> int:\n",
    "        #Review\n",
    "        length=len(citations)\n",
    "        def lower_bound(citations):\n",
    "            left=0;right=len(citations)-1\n",
    "            while left<=right:\n",
    "                #left左边小于，cita<长度，right右边大于等于，那left对应第一个大于等于\n",
    "                #找这个mid的位置，然后算有多少篇即可\n",
    "                mid=left+(right-left)//2\n",
    "                if citations[mid]<(length-mid):\n",
    "                    left=mid+1\n",
    "                else:\n",
    "                    right=mid-1\n",
    "            return left\n",
    "        return length-lower_bound(citations)\n",
    "                \n",
    "        \n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hIndex(self, citations: List[int]) -> int:\n",
    "        ans = 0\n",
    "        n = len(citations)\n",
    "        for h in range(n, -1, -1):\n",
    "            l, r = 0, n - 1\n",
    "            pian = 0\n",
    "            while l <= r:\n",
    "                mid = (l + r) // 2\n",
    "                if(citations[mid] >= h):\n",
    "                    r = mid - 1\n",
    "                else:\n",
    "                    l = mid + 1\n",
    "            pian = n - (r + 1)\n",
    "            if pian >= h:\n",
    "                ans = max(ans, h)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def hIndex(self, citations: List[int]) -> int:\n",
    "        n = len(citations)\n",
    "        left,right = 0,n-1\n",
    "        result=0\n",
    "        while right >= left:\n",
    "            mid = (left + (right-left)//2)\n",
    "            if citations[mid] >= n-mid:\n",
    "                 result=n-mid\n",
    "                 right=mid-1\n",
    "            else:\n",
    "                left=mid+1\n",
    "        return result\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
